﻿#include<iostream>
using namespace std;


struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
    void reorderList(ListNode* head)
    {
        // 处理边界情况
        if (head == nullptr || head->next == nullptr || head->next->next ==
            nullptr) return;
        // 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow 的落点在哪⾥）
        ListNode* slow = head, * fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 2. 把 slow 后⾯的部分给逆序 - 头插法
        ListNode* head2 = new ListNode(0);
        ListNode* cur = slow->next;
        slow->next = nullptr; // 注意把两个链表给断开
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        // 3. 合并两个链表 - 双指针
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        ListNode* cur1 = head, * cur2 = head2->next;
        while (cur1)
        {
            // 先放第⼀个链表
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;
            // 再放第⼆个链表
            if (cur2)
            {
                prev->next = cur2;
                prev = prev->next;
                cur2 = cur2->next;
            }
        }
        delete head2;
        delete ret;
    }
};
     

int main()
{
	return 0;
}